Lossy compression is widely used in signal processing and signal transmission. There are several applications of lossy signal compression, such as the compression of camera images, multispectral images, hyperspectral images, and synthetic aperture radar (SAR) data, to name a few. In such applications, the goal is to encode the signal with an encoder and use a small number of bits to represent the signal, such that the signal can be transmitted at a lower bit rate, at the expense of some distortion in the signal, i.e., there is some loss of information duting the compression, hence the compressions is lossy.
FIG. 1A is a block diagram of a conventional coding method and system. The system includes an encoder 110 and a decoder 120. The encoder takes as input an uncompressed sugnal 101 and produces a compressed signal 111. Lossless transmission 115 is used to transmit the compressed signal to the decoder, which produces a decompressed signal 121, which is an estimate of the uncompressed signal.
The goal of the encoder, i.e., the system or method performing the compression, is to produce a bitstream, i.e., a sequence of bits that represent the signal with as little distortion as possible for a given bit-rate. Alternatively the encoder might produce a bitstream with as few bits as possible given the distortion that can be tolerated by the application.
The decoder, i.e., the system or method decompressing the signal, uses the sequence of bits produced by the decoder to recover the original signal with as little distortion as possible for the given bit rate.
Most commonly used encoding methods use two techniques: prediction followed by transformation. The prediction tries to predict parts of the signal being encoded, e.g., blocks of an image, using information from other parts of a signal or other signals. Therefore, the encoder includes prediction parameters in the bitstream, i.e., how the prediction was performed, e.g., which part of the signal was used and which prediction method was used, so that the decoder can also perform the same prediction step.
Because the prediction is typically imperfect, there is a prediction residual that is also encoded. The hope is that the residual is easy to encode, so that when the rate used to transmit the prediction parameters and the rate used to code the residual is lower than simply encoding the signal without prediction.
To encode the residual, the encoder first uses a transformation, which maps the signal to a different domain that is simpler to encode. The goal of the transformation is to expose the structure of the signal such that the encoding requires a small number of bits. For example, image and video compression might transform the residual using a discrete cosine transform (DCT) because it is easier to encode the DCT coefficients of the residual than the residual itself, even though they both represent the same information. The reason is that the DCT concentrates the information to a few significant coefficients that are encoded.
Those two techniques are typically combined with other techniques that refine the performance of the encoder, e.g., by selecting how many bits of the bitstream to use for each part of the signal so that the trade off between rate and distortion is optimally traded throughout the signal.
Unfortunately, those encoding techniques produce very complex encoders, and, typically require very simple decoders. This is acceptable in many applications, such as image encoding, such as movies and videos. There, the encoder has essentially unlimited resources, and the decoer at the playback device has limited resources. However, in applications in which the encoder has to be limited computationally, this becomes problematic.
For example, the computational resources available for satellite image or radar signal compression is very limited due to restrictions on the processors and power that can withstand space travel conditions. Similarly, in applications, such as hyperspectral or multispectral image compression, the amount of data that need to be used for prediction and transformation require memory storage prohibitive for the state of the art portable devices. Even modern video compression in mobile devices, e.g., mobile telephones and other handheld devices, uses a separate processor to minimize the load on the main processor, and to reduce power consumption. For many of such applications, the computational resources and power available to the decoder are assentially unlimited. Hence, it makes sense to decrease the complexity of the encoder at the expensense of more complex decoders.
An alternative approach is distributed compression, also known in the art as compression with side information. This class of methods does not perform the prediction step at the encoder. Instead of the encoder predicting the signal and encoding the residual, the encoder assumes that the decoder is capable of preforming some prediction about the signal from side information available at the decoder. Because the prediction is based on the side information, it can be imperfect, and, therefore, the decoding can incur significant distortion. Thus, the role of the encoder is to transmit a bitstream that can be used with the prediction at the decoder to reduce the distortion of the decoded signal.
In practice, all practical coding with side information methods attempt to correct a bitstream. Specifically, the prediction method at the decoder attempts to predict a predicted bitstream that, when subsequently decoded further, can produce the decompressed signal. The encoder attempts to generate a transmitted bitstream that can correct the errors in the predicted bitstream to produce an error-free bitstream. The error-free bitstream is subsequently used for the reconstruction.
To encode the transmitted bitstream, the encoder still performs the transformation step but then uses error correcting codes (ECC) to encode information. Because the bitstream is available at the decoder through the prediction, it is only necessary to transmit a small amount of error-correcting information generated by the ECC, known as syndromes. Because the prediction step is performed at the decoder, the encoder complexity is significantly reduced. On the other hand, the decoder complexity increases significantly, making compression with side information applicable when the decoder can be a more powerful system than the encoder.
FIG. 1B shows a method and system for coding using syndromes and side information. The system includes an encoder 210 that takes input an uncompressed signal 201 to produce a compressed signal 211 or syndrome, which is transmitted losslessly 115 to a decoder 220, which produces a decompressed signal 221.
Although compression with side information reduces the load at the encoder, it still requires the transformation step in addition to the encoding step, which, in some cases, can be computationally complex.
Furthermore, because all practical compression methods use error correction and decode the bitstream separately, those methods ensure that the bitstream can be accurately corrected. If the methods fail to transmit sufficient error correcting information, then the decoding can fail and recover a signal that is unrelated to the original signal. In many cases, failure in the error correction might result to a bitstream that cannot be decoded.
For this reason, most practical methods transmit a larger number of syndrome bits than necessary, to guarantee the correction works, thus wasting bandwidth. In addition, the extra bits do not improve the distortion performance of the compression method. Alternatively, a feedback-based rate control system can be implemented on top of the compression system, which attempts decoding and, when unsuccessful, require more syndrome bits. This requires two-way communication between the encoder and the decoder, which is not possible in many applications.